COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.REQUIRE "206MAC.PUB[206,LSP]" source_file
C00003 00003	.hd206 FALL 1979
C00008 00004	.if false then begin "programs"
C00010 ENDMK
C⊗;
.REQUIRE "206MAC.PUB[206,LSP]" source_file;
.
.odd heading(,,{page}) ;
.even heading({page}, , ) ;
.
.LSPFONT
.basicops 
.
.allops
.itemmac 1;
.
.PORTION MAINPORTION
.
.hd206 FALL 1979
.page←1
.skip
.hw 0, |Oct. 5|

	Below are some expressions, given first in internal, then
in external notation.  You should evaluate these expressions, by
hand, according to the rules presented in Chapter I.  When you are done
go to LOTS and type the expressions (in internal form) 
to LISP and check the value returned against your answer.
If there is something you don't understand try "stepping" through the evaluation.  
(See the MACLISP manual, or LISP at LOTS.)
These exercises are to get you going and not to be handed in.

	Some of the expressions involve user defined programs.   The definitions
are given in Chapter I.  To save you some typing, the necessary definitions
have been collected in a file which may be read in by typing:

⊗⊗⊗$$(DSKIN (DSK |C.CS206|) HW0 F79).$⊗

.begin nofill 

.group
$$(QUOTE (A B C))$
$$(A B C)$
.apart

.group
$$(QUOTE (A . (B . C)))$    ;;;Note how LISP prints the value.
$$(A B . C)$
.apart

.group
$$(CADAR '((X (Y Z)) B C))$
⊗⊗qada $$((X (Y Z)) B C)$⊗
.apart

.group
$$(FRINGE '(A . B))$        ;;;⊗fringe is defined on page 17.
⊗⊗fringe $$(A . B)$⊗

$$(FRINGE '(A B))$
⊗⊗fringe $$(A B)$⊗
.apart

.group
$$(ASSOC 'X  '((Y . 1) (X . 5) (A . (1 2 3))))$	
⊗⊗assoc[$$X$, $$((Y . 1) (X . 5) (A 1 2 3))$]⊗
				;;;⊗assoc is defined on page 21
.apart

.group
$$(SUBST (CONS 1 NIL) '?X (CONS (CONS (CONS 'A 'B)'?X) NIL))$
⊗⊗subst[1 . qNIL, $$?X$, [[$$A$ . $$B$] . $$?X$] . qNIL]⊗
				;;;⊗subst is defined on page 16
.apart

.group
$$((LAMBDA (L) (LIST 'COND (LIST (CADR L) (CADDR L)) (LIST T (CADDDR L))))$
$$__'(IF (NULL NIL) NIL (CDR NIL)))$
⊗⊗[[λl: <$$COND$, <qad l, qadd l>, <qT, qaddd l>>]⊗
⊗⊗_[$$(IF (NULL qNIL) qNIL (CDR qNIL))$]]⊗
.apart

.group
$$(EVAL ((LAMBDA (L)$
$$_________(LIST 'COND (LIST (CADR L) (CADDR L)) (LIST T (CADDDR L))))$
$$______'(IF (NULL NIL) NIL (CDR NIL)) ))$

⊗⊗eval [[λl: <$$COND$, <qad l, qadd l>, <qT, qaddd l>>]⊗
⊗⊗______[$$(IF (NULL qNIL) qNIL (CDR qNIL))$]]⊗
.apart

.group
$$(EXTENSIONS '(B A) $
$$____________'((A B) (B A C D) (C B D E) (D B C E) (E C D F) (F E)))$

⊗⊗extensions[$$(B A)$,⊗
⊗⊗$$_________'((A B) (B A C D) (C B D E) (D B C E) (E C D F) (F E)))$]⊗

where  ⊗extensions is a program to compute all extensions of length 1 of
given path in a given graph.  (see page 2 for representation of graphs)

$$(DEFUN EXTENSIONS  (PATH GRAPH)$
$$____(MAPCAR (FUNCTION (LAMBDA (X) (CONS X PATH)))$
$$__________(CDR (ASSOC (CAR PATH) GRAPH))))$
 				;;;⊗mapcar is defined on page 23
.apart

.group
$$(DIFF '(TIMES X  (PLUS Y 3) 1) 'X)$  	;;;⊗diff is defined on page 24
⊗⊗diff[$$(TIMES X (PLUS Y 3) 1)$, $$X$]⊗
.apart
.end

The following expressions all contain some sort of error.  See if you
can find the error.  The type the expression to LISP so see what
sort of error message you get.   (Remember to type <control>G to
get out to the "break-loop" after an error occurs.)

.begin verbatim select 6 group

(ATOM A)
(CADR '((FOO.BAZ).GLUB))
(CONS '(A B) (CONS 'C))
(CONS ('(A B) 'C))
(COND (ATOM '(A.B) T) (T (CDR '(A.B))))
.end

.if false then begin "programs"

(DEFUN FRINGE (X) 
  (COND ((ATOM X) (LIST X)) (T (APPEND (FRINGE (CAR X)) (FRINGE (CDR X)))) ))

(DEFUN ASSOC (X A)
  (COND ((NULL A) NIL) ((EQ X (CAAR A)) (CAR A)) (T (ASSOC X (CDR A))) ))


(DEFUN SUBST (X Y Z)
  (COND ((ATOM Z) (COND ((EQ Y Z) X) (T Z) ))
	(T (CONS (SUBST X Y (CAR Z)) (SUBST X Y (CDR Z)))) ))

(SSTATUS PUNT NIL) 

(DEFUN MAPCAR (F U) (COND ((NULL U) NIL) (T (CONS (F (CAR U)) (MAPCAR F (CDR U)))) ))
(DEFUN MAPLIST (F U) (COND ((NULL U) NIL) (T (CONS (F U) (MAPLIST F (CDR U)))) ))

(DEFUN EXTENSIONS  (PATH GRAPH)
    (MAPCAR (FUNCTION (LAMBDA (X) (CONS X PATH)))
                      (CDR (ASSOC (CAR PATH) GRAPH))))

(DEFUN DIFF (E V) 
  (COND	((ATOM E) (COND ((EQ E V) 1) (T 0)))
	((EQ (CAR E) 'PLUS)
	 (CONS 'PLUS
	       (MAPCAR (FUNCTION (LAMBDA (X) (DIFF X V))) (CDR E))))
	((EQ (CAR E) 'TIMES)
	 (CONS 'PLUS
	       (MAPLIST (FUNCTION 
			  (LAMBDA (X) 
			    (CONS 'TIMES
				  (MAPLIST (FUNCTION 
					    (LAMBDA (Y) 
					      (COND ((EQ X Y) (DIFF (CAR Y) V))
						    (T (CAR Y)))))
					   (CDR E)))))
	                (CDR E))))))

.end "programs"